package com.chj.gaoji.class14;

//https://leetcode-cn.com/problems/count-of-range-sum/solution/327qu-jian-he-de-ge-shu-ti-jie-zong-he-by-xu-yuan-/
public class Code01_CountofRangeSum {

	int res = 0;
	int lower;
	int upper;

	public int countRangeSum(int[] nums, int lower, int upper) {

		if (nums.length == 0)
			return 0;
		long[] prefix = new long[nums.length];
		long sum = 0;
		for (int i = 0; i < nums.length; i++) {
			sum += nums[i];
			prefix[i] = sum;
		}
		this.lower = lower;
		this.upper = upper;
		sortMergeRecursionHelper(prefix, 0, prefix.length - 1);
		return res;
	}

	public void sortMergeRecursionHelper(long[] nums, int left, int right) {
		if (left == right) {
			if (nums[left] >= lower && nums[left] <= upper) {
				res++;
			}
			return;
		}

		int mid = left + (right - left) / 2;
		sortMergeRecursionHelper(nums, left, mid);
		sortMergeRecursionHelper(nums, mid + 1, right);

		mergeArr(nums, left, mid, right);
	}

	public void mergeArr(long[] nums, int left, int mid, int right) {

		// 计算部分
		int lowerIndex = mid + 1;
		int upperIndex = mid + 1;
		for (int i = left; i <= mid; i++) {
			while (lowerIndex <= right && nums[lowerIndex] - nums[i] < lower) {
				lowerIndex++;
			}
			while (upperIndex <= right && nums[upperIndex] - nums[i] <= upper) {
				upperIndex++;
			}
			res += upperIndex - lowerIndex;
		}

		// 排序部分
		long[] temp = new long[right - left + 1];
		int i = left, j = mid + 1, k = 0;
		while (i <= mid && j <= right) {
			temp[k++] = nums[i] < nums[j] ? nums[i++] : nums[j++];
		}
		while (i <= mid)
			temp[k++] = nums[i++];
		while (j <= right)
			temp[k++] = nums[j++];

		int index = 0;
		while (left <= right) {
			nums[left++] = temp[index++];
		}
	}
}
